1. Field of the Invention
Embodiments of the present invention generally relate to a low complexity large transform for video coding.
2. Description of the Related Art
Video compression, i.e., video coding, is an essential enabler for digital video products as it enables the storage and transmission of digital video. In general, video compression techniques apply prediction, transformation, quantization, and entropy coding to sequential blocks of pixels in a video sequence to compress, i.e., encode, the video sequence. Video decompression techniques generally perform the inverse of these operations in reverse order to decompress, i.e., decode, a compressed video sequence.
In the emerging next generation video coding standard currently under development by a Joint Collaborative Team on Video Coding (JCT-VC) established by the ISO/IEC Moving Picture Experts Group (MPEG) and ITU-T Video Coding Experts Group (VCEG) that is commonly referred to High Efficiency Video Coding (HEVC), discrete cosine transforms (DCT) are proposed with the following blocks sizes: 4×4, 8×8, 16×16, 32×32 and 64×64. While large block size transforms such as 16×16, 32×32 and 64×64 DCTs improve coding efficiency, using such transforms increases implementation complexity significantly.
In general, the complexity of transforms typically increases with O(Nlog(N)) for fast algorithms and O(N^3) for implementation with direct matrix multiplication. For example, in the HEVC test model under consideration, version 0.7.3 (TMuC-0.7.3), the implemented 16×16 transform requires 1408 multiplications and the implemented 32×32 transform requires 7424 multiplications, an almost 5× increase in complexity. A direct matrix multiplication implementation of a 16×16 transform requires 16^3 multiplications and a direct matrix multiplication implementation of a 32×32 transform requires 32^3 multiplications, an 8× increase in complexity. Accordingly, improvements in implementation complexity of large block transforms are needed to ensure the feasibility of HEVC implementations.